package de.tud.binpacking.heuristic.improvement;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

import de.tud.binpacking.data.Batch;
import de.tud.binpacking.data.Order;
import de.tud.binpacking.data.Solution;
import de.tud.binpacking.instance.Instance;

public class LocalSearchBestImprovement extends AImprovementHeuristic {

	public LocalSearchBestImprovement(Instance instance) {
		super(instance);
	}

	@Override
	public String toString() {
		return "Local Search : Best Improvement 2-Opt";
	}

	@Override
	public Solution improveSolution(Solution solution) {
		
		Map<Order, Batch> map = new HashMap<Order, Batch>();
		Set<Order> orders = new HashSet<Order>();
		orders.addAll(instance.getOrders());
		
		for(Batch batch : solution.getBatches()) {
			for(Order order : batch.getOrders()) {
				map.put(order, batch);
			}
		}
		
		double curCosts = solution.getCosts();
		double newCosts = curCosts;
		
		do {
			for(Order order1 : orders){
				for(Order order2 : orders){
					if(map.get(order1) == map.get(order2) || !map.get(order1).check(order1, order2)){
						continue;
					}
					
					Batch batch1 = map.get(order1);
					Batch batch2 = map.get(order2);
					
					newCosts = newCosts - batch1.getPathLength() - batch2.getPathLength();
					
					swap(batch1, order1, batch2, order2);
					
					newCosts = newCosts + batch1.getPathLength() + batch2.getPathLength();
					
					if (newCosts >= curCosts) {
						swap(batch1, order2, batch2, order1);
						newCosts = curCosts;
					} else {
						map.put(order2, batch1);
						map.put(order1, batch2);
						curCosts = newCosts;
					}
				}
			}
		} while (newCosts != curCosts);			

		return new Solution(map.values());
	}
	
	private static void swap(Batch batch1, Order order1, Batch batch2, Order order2) {
		batch1.getOrders().remove(order1);
		batch1.getOrders().add(order2);
		batch2.getOrders().remove(order2);
		batch2.getOrders().add(order1);
	}
}
